package com.lw.leetcode.stack.b;

import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * str
 * 880. 索引处的解码字符串
 *
 * @author liw
 * @version 1.0
 * @date 2021/11/20 14:36
 */
public class DecodeAtIndex {

    public static void main(String[] args) {
        DecodeAtIndex test = new DecodeAtIndex();

        // 0
//        String str = "leet2code3ef";
//
//        for (int i = 1; i < 39; i++) {
//            System.out.println(i + " " + test.decodeAtIndex(str, i));
//        }
//        int k = 1;

        // a
//        String str = "a2345678999999999999999";
//        int k = 1;

        // h
//        String str = "ha22";
//        int k = 5;


        // t
//        String str = "leet2dsf78co8df92";
//        int k = 15227;

        // c
//        String str = "a2b3c4d5e6f7g8h9";
//        int k = 10;

        // a
        String str = "ajx37nyx97niysdrzice4petvcvmcgqn282zicpbx6okybw93vhk782unctdbgmcjmbqn25rorktmu5ig2qn2y4xagtru2nehmsp";
        int k = 976159153;

        // a
//        String str = "ha22";
//        int k = 6;
//        for (int i = 8; i > 0; i--) {
//            String s = test.decodeAtIndex(str,i);
//            System.out.println(s);
//        }

        String s = test.decodeAtIndex(str, k);
        System.out.println(s);
    }


    public String decodeAtIndex(String s, int k) {
        Stack<Long> counts = new Stack<>();
        Stack<Integer> nums = new Stack<>();
        Stack<Integer> indexs = new Stack<>();
        counts.add(0L);
        nums.add(0);
        indexs.add(-1);
        int length = s.length();
        long item = 0;
        for (int i = 0; i < length; i++) {
            char c = s.charAt(i);
            if (c >= 'a') {
                item++;
                if (item == k) {
                    return String.valueOf(c);
                }
            } else {
                int n = c - '0';
                counts.add(item);
                item *= n;
                nums.add(n);
                indexs.add(i);
                if (item >= k) {
                    break;
                }
            }
        }
        while (!counts.isEmpty()) {
            long count = counts.pop();
            int n = nums.pop();
            int i = indexs.pop();
            if (count * n == k || count == k) {
                return find(s, i);
            } else if (count * n >= k) {
                k = (int) (k - k / count * count);
            } else {
                int t = (int) (k - count * n);
                return String.valueOf(s.charAt(i + t));
            }
            if (k == 0) {
                return find(s, i);
            }
        }
        return "";
    }

    private String find(String str, int index) {
        for (int i = index; i >= 0; i--) {
            char charAt = str.charAt(i);
            if (charAt >= 'a') {
                return String.valueOf(charAt);
            }
        }
        return "";
    }

}